package testFordFullkerson;

import java.util.HashSet;
import java.util.List;
import java.util.Set;
//http://blog.csdn.net/javaman_chen/article/details/8277161

//伪代码

/*
		for each edge(u, v)属于G.E(图G的边)
		(u, v).f = 0  //所有边的流为0
		//循环终止条件为残存我昂罗中不存在增广路径
		while s到t的残存网络中存在增广路径p:
		c(p) = 最小残存容量
		for 增广路径的每条边
		if 这条边属于E集合
		(u, v).f = (u, v).f + c(p)  //意思是在原有的流增加最小残存容量.
		else
		(u, v).f = (u, v).f - c(p)

		*/
public class FordFulkerson {
	private Set<Edge> path=new HashSet<Edge>();
	public int getMaxStream(String start,String end){
		while(hasAugmentPath(start,end)){
			int minRemain=getMinRemain(path);
			for(Edge edge:path){
				Edge reverseEdge=DataSource.getEdge(edge.getReversePath());//获取返回路径
				//计算当前流值
				if(edge.getRemain()>edge.getCapacity()){//残留值大于最大容量,表明该路径是残留网路中的路径
					if(edge.getRemain()>=reverseEdge.getCapacity()){//残留量大于返回路径的最大容量
						reverseEdge.setValue(reverseEdge.getCapacity());//返回路径设置成最大容量
						edge.setValue(edge.getRemain()-reverseEdge.getCapacity());
					}else{//残留量小于返回路径的最大容量
						reverseEdge.setValue(edge.getRemain());
						edge.setValue(0);
					}
				}else{
					edge.setValue(edge.getValue()+minRemain);
				}
				//计算残留值
				edge.setRemain(edge.getRemain()-minRemain);
				reverseEdge.setRemain(reverseEdge.getRemain()+minRemain);
			}
			path.clear();
		}
		return 0;
	}
	public void printStreamInfo(){
		List<Edge> edges=DataSource.nextEdge("S");
		int maxStream=0;
		for(Edge edge:edges){
			if(edge.getCapacity()!=0){
				maxStream+=edge.getValue();
			}
		}
		System.out.println("网路最大流为："+maxStream);
		System.out.println("流信息如下：");
		for(Edge edge:DataSource.getAllEdge()){
			if(edge.getCapacity()!=0){
				System.out.println(edge.getStart()+"->"+edge.getEnd()+"\t:\t"+edge.getValue());
			}
		}
	}
	private boolean hasAugmentPath(String start, String end) {
		for(Edge edge:DataSource.nextEdge(start)){
			if(path.contains(edge) || //出现回路 
					edge.getRemain()==0){//没有残余流量
				continue;
			}
			path.add(edge);
			if(edge.getEnd().equals(end)){
				return true;//找到增广路径
			}else{//深度递归
				if(hasAugmentPath(edge.getEnd(),end)){
					return true;
				}else{
					path.remove(edge);
					continue;
				}
			}
		}
		return false;//遍历结束,没有找到增广路径
	}
	/**
	 * 获取最小残留量
	 */
	private int getMinRemain(Set<Edge> edges){
		int res=Integer.MAX_VALUE;
		for(Edge edge:edges){
			if(edge.getRemain()<res){
				res=edge.getRemain();
			}
		}
		return res;
	}
}
